The invention generally relates to the art of telecommunications traffic management and more specifically to a method and apparatus for controlling traffic flows in a packet-switched network, especially an ATM network, in order to provide constant bit rate service performance.
The concept of a xe2x80x9ctraffic contractxe2x80x9d is well known to those skilled in the art of telecommunications network engineering. Basically, a user or end-station device agrees to transmit packets according to certain pre-defined or negotiated traffic parameters, and in return the network will provide a certain service performance. If, however, the traffic flow from the end-station to the network does not conform to the traffic parameters as specified by a pre-determined conformance algorithm, the network does not have to provide the requested service performance.
The negotiated characteristics of an ATM connection are specified in ATM traffic management protocols, for instance the ATM Forum Traffic Management Specification, Version 4.0, doc. no. af-tm-0056.000, April 1996, which is incorporated herein by reference. These negotiated characteristics include:
(a) the desired service category and QoS parameters, such as the cell loss ratio and delay;
(b) the traffic descriptor, comprising, for instance, the PCR and CDVT, discussed in greater detail below; and
(c) the conformance definition used to unambiguously specify the conforming cells of the connection.
One service category defined by the ATM traffic management protocol is the constant bit rate (CBR) service which provides a connection a static amount of bandwidth that is continuously available during the lifetime of the connection. The requested bandwidth is characterized by the Peak Cell Rate (PCR) value. Another service category is the unspecified bit rate (UBR) service category which also includes a PCR value that the network may try, but does not guarantee, to meet. The PCR is explicitly stated for each ATM connection request. For instance, a switched virtual connection (SVC) call setup message includes an information element (IE) specifying the PCR value.
The CDVT or Cell Delay Variation Time, is a measure of the maximum allowed burstiness of a CBR connection. When packets or cells from two or more connections are multiplexed in a node, cells from a given connection may be delayed while cells of another connection are inserted at the output of the multiplexer. Similarly, some cells may be delayed while physical layer overhead cells are inserted. Consequently, with reference to the peak emission interval, T, which is the inverse of the contracted PCR, some randomness may affect the inter-arrival time between consecutive cells of a connection as monitored at the user-to-network interface (UNI). The upper bound on the degree of permissible clumping or burstiness is the CDVT parameter. Presently, this parameter is not explicitly negotiated when a connection request is received by the network, but rather is implicitly negotiated at subscription time.
The ATM conformance definition employs the Generic Cell Rate Algorithm (GCRA) which is used to define, in an operational manner, the relationship between the PCR and CDVT. The GCRA is defined with two parameters, the Increment, I, and the Limit, L. For CBR service, I=T=1/PCR, and L=CDVT. The GCRA determines for each cell arrival whether or not the cell conforms to the traffic contract of the connection. The GCRA is illustrated in FIG. 1 (original source: page 63 of ATM Forum Traffic Management Specification, Version 4.0, doc. no. af-tm-0056.000, April 1996). The GCRA is equivalent to a leaky bucket controller (LBC) algorithm. Specifically, a stream is GCRA(I, L) conformant if it conforms to an LBC with bucket size   σ  =      1    +          L      I      
and token rate   ρ  =            1      I        .  
It should be noted that an LBC controller with parameters ("sgr",xcfx81) ensures that the largest number of conformant cells between any two instances of time t1 and t2 is no more than "sgr"+xcfx81*(t2xe2x88x92t1).
An end-station device can be modelled as sourcing a plurality of traffic connections. For example, a wide-area-network may comprise two local-area-networks which are connected through a public ATM network. Each local-area-network comprises a number of workstations which are linked through a concentrator device that multiplexes the traffic streams from the various workstations for transmission over the ATM network. Since a key element of the traffic contract from the perspective of the user or end-station, e.g., the concentrator, is the sequence of cells sent to the network, the end-station will typically employ a scheduler or virtual shaping device which processes the multiplexed source cell stream such that the resultant output toward the network conforms to the traffic parameters specified in the traffic contract.
At the other side of the user-to-network interface, the network typically includes a connection admission control (CAC) function in order to determine whether a connection request should be admitted or denied. As discussed above, a connection request typically defines the source traffic parameters and the requested service performance or quality of service (QoS) class. For a switched connection such as an SVC the connection request occurs at call origination time, and for a permanent connection such as a PVC the connection request occurs when the permanent connection is provisioned. The CAC will only accept the connection request provided that the QoS for existing connections would still be met if the new request is accepted. CAC is typically carried out on a node-by-node basis for switched connections and through a centralized bandwidth management system for permanent connections. For accepted connection requests, CAC determines the configuration of the traffic conformance algorithm, routing, and resource allocation, including trunk bandwidth, buffer space, and internal node resources. It will be appreciated that in order to achieve high switching rates, the CAC must be simple and operate very rapidly.
Once the connection is accepted, the network must typically monitor the connection at the end-station access in order to protect network resources from behaviour which can affect the QoS of other already established connections. This is accomplished by detecting violations of negotiated parameters and taking appropriate actions. In ATM standards, this function is commonly termed Usage Parameter Control (UPC). The UPC typically employs the GCRA for monitoring the connection. However, there are some instances where UPC cannot be applied at the periphery of a network for various reasons.
Network node elements also have the problem of having to shape traffic flows. This is because a network element has to schedule incoming packets or cells from a variety of connections or queues into an outgoing link which interconnects a counterpart network element. The scheduler, arbiter or virtual shaping device of a network element must employ an effective service discipline in order to meet different levels of QoS and bandwidth requirements. For example, the receiving network element may accept only a certain degree of packet clumping or burstiness, i.e., packet or cell delay tolerance, otherwise buffers on the receiving network element would overflow. The network scheduler, arbiter or virtual shaping device should also ideally operate very rapidly in order to achieve high switching rates.
Generally speaking, the invention provides a method and related apparatus for scheduling packets in a non-work conserving manner at a queueing point in order to minimize, or at least quantify, the maximum burstiness or jitter of a packet stream.
According to one aspect of the invention, a data communication method is provided for use in a packet-switched network. The method comprises:
(a) receiving packets from a traffic source, such as a connection, and queuing the packets in a memory;
(b) defining a repeating scheduling frame having a duration FD and a total of FL slots;
(c) maintaining an ordered list of free slots;
(d) determining a number, Nnew, of slots needed to satisfy the bandwidth requirement of the traffic source;
(e) identifying a set {I[0], I[1], I[2] . . . I[Nnewxe2x88x921]} of ideal slot positions for the traffic source which are spaced apart from each other by a time substantially equal to a peak emission interval between the packets;
(f) selecting a set of assigned slot positions, {VC[0], VC[1], VC[2], . . . , VC[Nnewxe2x88x921]}, from the list of free slot positions to the connection, wherein the set of ideal slot positions and the set of assigned slot positions have an ordinal one-to-one correspondence and wherein each assigned slot position of the set of assigned slot positions has a position which is approximate or equal to, respectively, its corresponding ideal slot position of the set of ideal slot positions, and wherein each VC[i], where i xcex5{1, 2, . . . Nnewxe2x88x921}, is selected from the list of free slot positions so as not to increase the overall burstiness of the connection, and in the event such a free slot position of the list of free slot positions does not exist for a given VC[i], the VC[i] is selected from the list of free slot positions so as to least increase the overall burstiness of the connection; and
(g) retrieving the queued packets from the memory and transmitting the retrieved packets only during the relative time periods represented by the assigned slots.
In the preferred embodiment, the overall burstiness of the connection is defined by the quantity (ME+ML)*FD/FL, wherein ME corresponds to a maximum time by which any assigned slot VC[j] is earlier than a corresponding ideal slot I[j], j xcex5{0,1,2, . . . Nnewxe2x88x921}, and ML corresponds to a maximum time by which any assigned slot, VC[k], is later than a corresponding ideal slot I[k], k xcex5{0,1, 2, . . . Nnewxe2x88x921}. In the preferred embodiment, the computational complexity for determining slot assignments for a new connection is proportional to FL, the total number of slots in the frame.
According to another aspect of the invention, a method is provided for determining whether a traffic source which has been assigned a set {C[0], C[1], . . . C[Nnewxe2x88x921]} of slots in an FL, FLxe2x89xa7Nnew, slot scheduling frame of duration FD conforms to a GCRA characterized by a peak packet emission interval, T, and a packet delay variation time, CDVT. The method comprises:
(a) selecting a set {I[0], I[1], . . . I[Nnewxe2x88x921]} of ideal slot positions for the traffic source wherein every slot I[j] is spaced apart from slot I[jxe2x88x921], j xcex5{1, 2, . . . Nnewxe2x88x921}, by a time substantially equal to T;
(b) selecting a maximum-valued element, ME, of the set {I[k]xe2x88x92C[k]: k xcex5{0,1, . . . Nnewxe2x88x921}}, and if this is a negative number, setting ME to zero;
(c) selecting a maximum-valued element, ML, of the set {C[k]xe2x88x92I[k]: k xcex5{0, 1, . . . Nnewxe2x88x921}}, and if this is a negative number, setting ML to zero; and
(d) comparing the quantity (ME+ML)*FD/FL against the CDVT and in response thereto concluding whether the connection conforms to the GCRA.
This aspect of the invention can be used in conjunction with the preferred first mentioned aspect of the invention to iteratively determine, while the slots for a new traffic source are being assigned, whether the new connection will be GCRA conformant. Thus, the invention enables the admittance or rejection of new traffic sources based on whether the calculated CDVT (jitter) exceeds a pre-specified limit. Furthermore, since the complexity of the algorithm is linear in FL, the total number of slots in the frame, this allows for a relatively rapid connection admission control decision.
Another aspect of the invention provides a method for assigning slots in a TDMA frame to a traffic source, wherein the frame has a duration FD and a total of FL slots. The method includes:
(a) determining a number, Nnew, of slots needed to satisfy the bandwidth requirement of the traffic source;
(b) identifying a list A[i]: ixcex5{0, 1, . . . , Nnewxe2x88x921} of preferred slot positions;
(c) assigning a list C[i]: ixcex5{0, 1, . . . , Nnewxe2x88x921} of slots from a predetermined ordered list B of slots for the traffic source which approximate or equal the preferred slot positions, C[i]∀i being selected to be a slot in B which does not increase the overall burstiness of said traffic source, and in the event such a slot does not exist, a slot in B which least increases the overall burstiness of the traffic source; and
(d) removing the entries of C from B.
This aspect of the invention can be employed to assign slots to a previously inactive traffic source; i.e., one having no slots allocated thereto. In this case, A is set to a list of ideal slot positions for said traffic source which are spaced apart from each other by a time substantially equal to a peak emission interval between data packets of said traffic source, and B is set to an ordered list of free slots in the frame.
This aspect of the invention can also be employed to assign slots to an active traffic source which requests a reduction in bandwidth. In this case, the traffic source has M slots previously assigned thereto; and Nnew less than M. A is set to a list of ideal slot positions for the traffic source which are spaced apart from each other by a time substantially equal to a peak emission interval between data packets of the traffic source, and B is set to a list of the M slots previously assigned to the traffic source. This restricts the assigned slots to those previously allocated to the traffic source and may aid in minimizing disruption.
This aspect of the invention can also be employed to assign slots to an active traffic source which requests an increase in bandwidth. In this case, the traffic source has M slots previously assigned thereto, and Nnew greater than M. Steps (c)-(d) are preferably carried out two times. The first time, A is set to a list P of the M slots previously assigned to the traffic source and B is set to a list of ideal slot positions I for the traffic source which are spaced apart from each other by a time substantially equal to a peak emission interval between the packets of the traffic source to thereby delete from I those ideal slot positions which are nearest to corresponding slot positions in A and create a list Ixe2x80x2. The second time steps (c) and (d) are carried out A is set to Ixe2x80x2 and B is set to a list of free slot positions. Thereafter, the traffic source is assigned the slots listed in C (as determined the second time) and P. Thus, the assigned slots are those that were previously allocated to the traffic source plus a number of new slots needed to increase the bandwidth to the traffic source.